思路
一道kmp的裸题，主要是学习kmp的使用方法。kmp的精髓在于使用了一个next数组。这个next数组的计算是放在预处理中的。next数组中记录的是不同长度下最长的前后缀的位置。举个例子：
字符串：a b c d a b d
next 0 0 0 0 1 2 0
你看到了什么？后边的两个a，b对应了开头的公共前缀的长度。那么这个next数组该怎么用？当你做字符串匹配的时候，如果发现当前位置字符与模板字符串不同，那么你可以把指向模板字符串的指针挪到之前公共长度（也就是next数组对应的地方）继续匹配，这样就避免了公共的前缀重复匹配浪费时间。
这里着重讲一下next数组怎么求。next数组的求法稍微有点绕，我放下我的代码
void makenext() {
int q, k;
nexts[0] = 0;
for (q = 1, k = 0;q < m;q++) { while (k > 0 && b[q] != b[k])k = nexts[k - 1];
if (b[q] == b[k])k++;
nexts[q] = k;
}
}
代码中的while循环是非常绕的，他的意思是什么呢？在求前后缀的时候，因为b[q]!=b[k]，也就是前后缀有失配的地方，这个时候你之前算的一长串已经不能用了，所以你要回到之前求的短串再来尝试匹配。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
int nexts[10000], a[1000000], b[10000], n, m;
void makenext() {
int q, k;
nexts[0] = 0;
for (q = 1, k = 0;q < m;q++) {
while (k > 0 && b[q] != b[k])k = nexts[k - 1];
if (b[q] == b[k])k++;
nexts[q] = k;
}
}
int kmp() {
int i, q;
makenext();
for (i = 0, q = 0;i < n;i++) {
while (q > 0 && b[q] != a[i])q = nexts[q - 1];
if (b[q] == a[i])q++;
if (q == m)break;
}
return i-q+2;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--) {
cin >> n >> m;
for (int i = 0;i < n;i++)cin >> a[i];
for (int i = 0;i < m;i++)cin >> b[i];
int flag = kmp();
if (flag == n )cout << -1 << "\n";
else cout << flag << "\n";
}
return 0;
}